Random numbers, which are referred to as the result of random elements, are required for many applications. So-called random number generators are used to generate random numbers. Random number generators are methods which supply a sequence of random numbers. A crucial criterion of random numbers is whether the result of the generation may be regarded as being independent of earlier results.
Random numbers are required for cryptographic methods, for example. These random numbers are used to generate keys for the encryption methods. Random number generators (RNGs) are used, for example, to generate master keys for symmetric encryption methods and handshake protocols in elliptic curve cryptography (ECC), which prevent a performance analysis attack and replay attacks.
There are two fundamental types of RNGs, namely pseudo random number generators for high throughputs and low security levels. Typically, a secret value is entered into a PRNG, and each input value will always result in the same output series. However, a good PRNG will output a number series which appears to be random and will pass the majority of tests.
Keys for cryptographic methods are subject to high requirements in terms of the randomness properties. Pseudo random number generators (PRNG), for example, represented by a linear feedback shift register (LFRS), are therefore not suitable for this purpose. Only a true random number generator (TRNG) meets the requirements at hand. This generator uses natural noise processes to obtain an unpredictable result. Noise generators which use the thermal noise of resistors or semiconductors or the shot noise at potential barriers, such as at p-n junctions, are common. Another option is the use of radioactive decay of isotopes.
While “traditional” methods use analog elements, such as resistors, as noise sources, digital elements, such as inverters, have been used frequently in the more recent past. These have the advantage of lower complexity in the circuitry layout since these are available as standard elements. In addition, such circuits may also be used in freely programmable circuits, such as FPGAs.
For example, the use of ring oscillators which represent an electronic oscillator circuit is known. In these, an odd number of inverters is interconnected to form a ring, whereby an oscillation having a natural frequency is created. The natural frequency depends on the number of inverters in the ring, the properties of the inverters, the conditions of the interconnection, namely the line capacitances, the operating voltage and the temperature. Due to the noise of the inverters, a random phase displacement occurs as compared to the ideal oscillator frequency, which is used as a random process for the TRNG. It must be noted that ring oscillators oscillate independently and do not require any external components, such as capacitors or coils.
The output of the ring oscillators is typically compressed or subjected to post processing to compress or pool the entropy and eliminate any bias.
One problem with the use of randomness arises in that the ring oscillator must be sampled, preferably in the vicinity of an anticipated ideal edge to obtain a random sample value. The publication by Bock, H., Bucci, M., Luzzi, R.: An Offset-compensated Oscillator-based Random Bit Source for Security Applications, CHES 2005, shows an option of how sampling is always carried out in the vicinity of an oscillator edge by the controlled shifting of the sampling point in time.
A method for generating random numbers with the aid of a ring oscillator is known from the publication European Patent No. 1 686 458, in which a first and a second signal are provided, the sampling of the first signal being triggered by the second signal. In the described method, a ring oscillator is sampled multiple times, always using only non-inverting delays, namely an even number of inverters as delay elements. Starting from a starting point, the oscillator ring is always sampled after an even number of inverters simultaneously or with mutual delay. In this way, the shift of the sampling point in time may be dispensed with; instead, the multiple sampling signals are evaluated.
The publication “Design of Testable Random Bit Generators” by Bucci, M. and Luzzi, R. (CHES 2005) introduces a method with which an influence on the random source may be detected. Attacks may thus be prevented. However, it does not allow a direct distinction between random values and deterministic values.
Another option is provided by the use of multiple ring oscillators. This is demonstrated in the publication Sunar, B. et al: Aproveable Secure True Random Number Generator with Built In Tolerance Attacks, WEE Trans. on Computers, 1/2007, for example. Here, sample values of multiple ring oscillators are concatenated to each other and evaluated.
The problem here is that correlations between the ring oscillators may occur, for example due to outside influences, so that the results obtained do not have a desired degree of entropy.
This problem is addressed by the present invention which is described hereafter, one focus being an implementation in an FPGA.
All high quality ASIC-based TRNGs are designed specifically for the customer, which means that the gates are placed and connected manually. This allows the developer to ensure many desired properties of the TRNG. Otherwise, the frequency and the jitter could not be adhered to. Above all, the quality of the random output must be high. Many statistical tests have been developed to check this. It should be noted that the performance capability of the TRNG may vary drastically as a function of the design. A test for checking the quality of the TRNG on the ASIC in real time has not existed previously.
Test circuits are able to detect special types of fault attacks. This is important in particular with FPGAs. An injected fault may not only temporarily change the functionality of an FPGA, but may also change stored bits in the SRAM of the LUT, which may permanently change the entire FPGA configuration. The SRAM of the LUT is sensitive in particular to radiation. LUT is a look up table in which the function value is stored as a function of the input bits. This table is stored in a static RAM (SRAM).
It is furthermore known to add RC filters to the supply lines to prevent frequency injection attacks. However, this is not possible with FPGAs.